//给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 
//的一条无向边，且该边遍历成功的概率为 succProb[i] 。 
//
// 指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。 
//
// 如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。 
//
// 
//
// 示例 1： 
//
// 
//
// 输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, 
//end = 2
//输出：0.25000
//解释：从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25
// 
//
// 示例 2： 
//
// 
//
// 输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, 
//end = 2
//输出：0.30000
// 
//
// 示例 3： 
//
// 
//
// 输入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
//输出：0.00000
//解释：节点 0 和 节点 2 之间不存在路径
// 
//
// 
//
// 提示： 
//
// 
// 2 <= n <= 10^4 
// 0 <= start, end < n 
// start != end 
// 0 <= a, b < n 
// a != b 
// 0 <= succProb.length == edges.length <= 2*10^4 
// 0 <= succProb[i] <= 1 
// 每两个节点之间最多有一条边 
// 
// Related Topics图 | 最短路 | 堆（优先队列） 
//
// 👍 105, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

class PathWithMaximumProbability {
    public static void main(String[] args) {
        Solution solution = new PathWithMaximumProbability().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
            // 无向图变成有向图
            List<double[]>[] graph = new LinkedList[n];
            for (int i = 0; i < graph.length; i++) {
                graph[i] = new LinkedList<>();
            }

            for (int i = 0; i < edges.length; i++) {
                int from = edges[i][0];
                int to = edges[i][1];
                graph[from].add(new double[]{(double) to, succProb[i]});
                graph[to].add(new double[]{(double) from, succProb[i]});
            }

            return dijkstra(start, end, graph);
        }

        class Status {
            // 表示当前节点
            int id;
            // 从 start 节点到达当前节点的概率
            double probFromStart;

            public Status() {
            }

            public Status(int id, double probFromStart) {
                this.id = id;
                this.probFromStart = probFromStart;
            }
        }

        // 逆向处理dijkstra，返回的是最大的路径
        double dijkstra(int start, int end, List<double[]>[] graph) {
            int n = graph.length;
            double[] disTo = new double[n];
            Arrays.fill(disTo, -1);
            // 按照从大到小排序
            PriorityQueue<Status> queue = new PriorityQueue<Status>((a, b) -> Double.compare(b.probFromStart, a.probFromStart));
            // base case，start 到 start 的概率就是 1
            disTo[start] = 1;
            queue.offer(new Status(start, 1));

            while (!queue.isEmpty()) {
                Status status = queue.poll();
                int curId = status.id;
                double probFromStart = status.probFromStart;

                // 找到终点
                if (curId == end) return probFromStart;

                if (disTo[curId] > probFromStart) continue;

                for (double[] neighbor : graph[curId]) {
                    int nextId = (int) neighbor[0];
                    // 看看从 curNode 达到 nextNode 的概率是否会更大
                    double probFromNext = neighbor[1] * disTo[curId];
                    if (disTo[nextId] < probFromNext) {
                        disTo[nextId] = probFromNext;
                        queue.offer(new Status(nextId, probFromNext));
                    }
                }
            }

            // 如果到达这里，说明从 start 开始无法到达 end，返回 0
            return 0.0;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
